/**
 * Pow(x, n)
 *
 * 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
 *
 * 示例 1：
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 *
 * 示例 2：
 * 输入：x = 2.10000, n = 3
 * 输出：9.26100
 *
 * 示例 3：
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2-2 = 1/22 = 1/4 = 0.25
 *
 * 提示：
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * n 是一个整数
 * 要么 x 不为零，要么 n > 0 。
 * -104 <= xn <= 104
 */

/**
 * 快速幂算法, 我们要想求一个数的几次幂, 我们可以发现好几个数都是一直连乘连乘
 * 于是我们就可以将这些数一分为二, 这样我们把两边的数再相乘, 就是结果, 还将时
 * 间复杂度对半砍了, 于是我们继续这个步骤, 时间又多半砍
 * 时间复杂度 : O(log(n))
 * 空间复杂度 : O(log(n))
 */

public class Main {
    public double myPow(double x, int n) {

        // if (nn == 0) {
        //     return 1;
        // }

        // long n = nn;

        // 这里我们判断 n 是负数还是正数, 我们在后面的处理中, 一律用正数来处理
        // 还有一个细节, 就是我们要考率最小的负数转化为正数是会越界的, 于是我们
        // 呢要将 int 转为 Long 就可以解决了, 这也是这种问题的常见解决方法

        // 这里最大的负数是不能转化成 -n 的 因为这个时候, n 还是 int, 想要转化为 int 需要提前 定义 long
        return n > 0 ? dfs(x, n) : 1.0 / dfs(x, -n);
    }

    // 函数 (会超时)
    private double dfs1(double x, long n) {

        // 这里的出口条件是 n == 0, 不是 == 1
        // 因为 n == 1 时, 我们不会将最后面的数乘原来的, n 由 2 -> 1
        // 然后会直接从这出去, 然后 由第一个 if 条件返回, 最后面的底数是 1
        // 所以我们的出口得是 n == 0
        // 这样才会从第二个条件返回
        if (n == 0) {
            return 1.0;
        }

        if (n % 2 == 0) {

            // n 为偶数时, 我们将将这个数原乘, 并将 n / 2
            return dfs(x, n / 2) * dfs(x, n / 2);
        } else {

            // n 为奇数时, 我们让他乘以自身, 并使 n - 1
            // 这里我们需要 原来的数, 所以我们的函数中不能改变原来的数
            return x * dfs(x, n - 1);
        }
    }

    // **************************************
    // 记忆话搜索
    private double dfs(double x, long n) {

        // if (n == 1) {
        //     return x;
        // }

        if (n == 0) {
            return 1.0;
        }

        // 这里可以用记忆化搜索记录这个值
        // 这样后续也就不用在算一遍
        double half = dfs(x, n / 2);

        if (n % 2 == 0) {

            // n 为偶数时, 我们将将这个数原乘, 并将 n / 2
            return half * half;
        } else {

            // n 为奇数时, 因为 n / 2 会丢失 1, 我们让他乘以自身
            return half * half * x;
        }
    }


     public static void main(String[] args) {
         Main test = new Main();
         System.out.println(test.myPow(2.0, 10));
     }
}